#include<stdio.h>
void merge_sort(int*arr,int left,int right)
{
  int mid=(left+right)/2;
  int b[100];
  int t=left,k=mid+1;
  int size=0,num=right-left+1;
  while(left<=mid&&k<=right)
  {
    if(arr[left]<arr[k])
    {
      b[size++]=arr[left++];
    }
    else
    {
      b[size++]=arr[k++];
    
    }
  }
  if(left>mid)
  {
    for(;k<=right;++k)
    {
      b[size++]=arr[k];
    }
  }
  if(k>right)
  {
    for(;left<=mid;++left)
    {
      b[size++]=arr[left];
    }
  }
  for(int i=0;i<num;++i)
  {
    arr[t++]=b[i];
  }
}
void merge(int*arr,int left,int right)
{
  if(left==right)
  {
    return;
  }
  if(left<right)
  {   
    int mid=(left+right)/2;
    merge(arr,left,mid);
    merge(arr,mid+1,right);
    merge_sort(arr,left,right);
  }
}
int main()
{
  int arr[]={9,8,7,6,5,4,3,2,1};
  int n=sizeof(arr)/sizeof(arr[0]);
  merge(arr,0,n-1);
  for(int i=0;i<n;++i)
  {
    printf("%d ",arr[i]);
  }
  return 0;
}
